lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/java/io_estandar.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{import}}\ java\textcolor{BrickRed}{.}util\textcolor{BrickRed}{.*;} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{import}}\ java\textcolor{BrickRed}{.}io\textcolor{BrickRed}{.*;} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{import}}\ java\textcolor{BrickRed}{.}math\textcolor{BrickRed}{.*;} \\
   8 \mbox{}\  \\
   9 \mbox{}\textbf{\textcolor{Blue}{class}}\ Main\ \textcolor{Red}{\{} \\
  10 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{public}}\ \textbf{\textcolor{Blue}{static}}\ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{(}String\textcolor{BrickRed}{[]}\ args\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{throws}}\ IOException\ \textcolor{Red}{\{} \\
  11 \mbox{}\ \ \ \ \ \ \ \ BufferedReader\ reader\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{new}}\ \textbf{\textcolor{Black}{BufferedReader}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{new}}\ \textbf{\textcolor{Black}{InputStreamReader}}\textcolor{BrickRed}{(}System\textcolor{BrickRed}{.}in\textcolor{BrickRed}{));} \\
  12 \mbox{}\ \ \ \ \ \ \ \ String\ line\ \textcolor{BrickRed}{=}\ reader\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{readLine}}\textcolor{BrickRed}{();} \\
  13 \mbox{}\ \ \ \ \ \ \ \ StringTokenizer\ tokenizer\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{new}}\ \textbf{\textcolor{Black}{StringTokenizer}}\textcolor{BrickRed}{(}line\textcolor{BrickRed}{);} \\
  14 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ N\ \textcolor{BrickRed}{=}\ Integer\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{valueOf}}\textcolor{BrickRed}{(}tokenizer\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{nextToken}}\textcolor{BrickRed}{());} \\
  15 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}N\textcolor{BrickRed}{-\/-}\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  16 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ String\ a\textcolor{BrickRed}{,}\ b\textcolor{BrickRed}{;} \\
  17 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ a\ \textcolor{BrickRed}{=}\ reader\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{readLine}}\textcolor{BrickRed}{();} \\
  18 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ b\ \textcolor{BrickRed}{=}\ reader\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{readLine}}\textcolor{BrickRed}{();} \\
  19 \mbox{}\  \\
  20 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ A\ \textcolor{BrickRed}{=}\ a\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{length}}\textcolor{BrickRed}{(),}\ B\ \textcolor{BrickRed}{=}\ b\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{length}}\textcolor{BrickRed}{();} \\
  21 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}B\ \textcolor{BrickRed}{$>$}\ A\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  22 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ System\textcolor{BrickRed}{.}out\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{println}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}0"{}}}\textcolor{BrickRed}{);} \\
  23 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  24 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ BigInteger\ dp\textcolor{BrickRed}{[][]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{new}}\ BigInteger\textcolor{BrickRed}{[}\textcolor{Purple}{2}\textcolor{BrickRed}{][}A\textcolor{BrickRed}{];} \\
  25 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{/*}} \\
  26 \mbox{}\textit{\textcolor{Brown}{dp[i][j]\ =\ cantidad\ de\ maneras\ diferentes}} \\
  27 \mbox{}\textit{\textcolor{Brown}{en\ que\ puedo\ distribuir\ las\ primeras\ i}} \\
  28 \mbox{}\textit{\textcolor{Brown}{letras\ de\ la\ subsecuencia\ (b)\ terminando}} \\
  29 \mbox{}\textit{\textcolor{Brown}{en\ la\ letra\ j\ de\ la\ secuencia\ original\ (a)}} \\
  30 \mbox{}\textit{\textcolor{Brown}{*/}} \\
  31 \mbox{}\  \\
  32 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{charAt}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{charAt}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{))}\textcolor{Red}{\{} \\
  33 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}\textcolor{Purple}{0}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ BigInteger\textcolor{BrickRed}{.}ONE\textcolor{BrickRed}{;} \\
  34 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  35 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}\textcolor{Purple}{0}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ BigInteger\textcolor{BrickRed}{.}ZERO\textcolor{BrickRed}{;} \\
  36 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  37 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$}A\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  38 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{];} \\
  39 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{charAt}}\textcolor{BrickRed}{(}j\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{charAt}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{))}\textcolor{Red}{\{} \\
  40 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{add}}\textcolor{BrickRed}{(}BigInteger\textcolor{BrickRed}{.}ONE\textcolor{BrickRed}{);} \\
  41 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  42 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  43 \mbox{}\  \\
  44 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}B\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  45 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}\textcolor{Purple}{0}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ BigInteger\textcolor{BrickRed}{.}ZERO\textcolor{BrickRed}{;} \\
  46 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$}A\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  47 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{];} \\
  48 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{charAt}}\textcolor{BrickRed}{(}j\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{charAt}}\textcolor{BrickRed}{(}i\textcolor{BrickRed}{))}\textcolor{Red}{\{} \\
  49 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{add}}\textcolor{BrickRed}{(}dp\textcolor{BrickRed}{[(}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{)\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{]);} \\
  50 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  51 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  52 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  53 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ System\textcolor{BrickRed}{.}out\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{println}}\textcolor{BrickRed}{(}dp\textcolor{BrickRed}{[(}B\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)\%}\textcolor{Purple}{2}\textcolor{BrickRed}{][}A\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{toString}}\textcolor{BrickRed}{());} \\
  54 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  55 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  56 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  57 \mbox{}\textcolor{Red}{\}} \\
  58
  59 } \normalfont\normalsize